



		CANADA TOUR - SOLUTIE
	       -----------------------

	Vom folosi metoda programarii dinamice. Problema este echivalenta cu determinarea
a 2 drumuri independente, ce merg numai spre est de la cel mai vestic la cel mai estic
oras (independente in sensul ca singurele puncte comune pot fi doar primul si ultimul oras),
circuitul cerut constand din primul drum,urmat de al doilea parucrs invers.
	Numerotam orasele de la vest spre est cu 1,2,..,n.
	Definim o functi de cost in modul urmator: c[i,j]= nr. maxim de orase de pe
doua drumuri independente ce ajung din 1 in i si j. Functia se calculeaza astfel:

c[1,1]=1
- pt. orice i<j vom pune: c[i,j]= max c[i,k]+1, k<j (k,j) muchie ci c[i,k]>0

	O data cu atribuirea unei valori cui c[i,j] se va atribui aceeasi valoare si
lui c[j,i]. Se observa ca elementele lui c vor primi valori parcurgand matricea pe
linii in partea de deasupra diagonalei.
	Pt. a determina costul cerut vom pune:

cost = max {c[i,n] | (i,n) muchie }

	Daca cost=0, atunci nu exista nici o pereche de drumuri independente de la
1 la n, deci problema nu are solutie si circuitul optim trece prin cost orase. Daca
problema are solutii, o solutie optima se determina dupa astfel:

- notam cu H1 si H2 ultimele orase de pe cele 2 drumuri; la inceput
H2=n, iar H1=i, unde c[i,n]=cost, (i,n)=muchie. 

In continuare cautam in mod repetat:
- un nou H2 (notat cu h) daca H1>H2; h va fi ales astfel incat
c[H1,h]+1=c[H1,H2] -> H1 va primi valoarea h
- un nou H1 (notat cu H) daca H1>H2; h va fi ales astfel incat
c[h,H2]+1=c[H1,H2] si poi H2 va primi valoarea H

- pana cand H1=H2=1